package 力扣._00周赛._144双周赛.问题3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int maxRemoval(int[] nums, int[][] queries) {
        // 差分数组
        int[] diff = new int[nums.length + 1];
        for (int[] query : queries) {
            diff[query[0]]++;
            diff[query[1] + 1]--;
        }
        // 对应真实数组
        int[] real = new int[nums.length];
        real[0] = diff[0];
        for (int i = 1; i < nums.length; i++) {
            real[i] = real[i - 1] + diff[i];
        }
        // 得到多余值
        for (int i = 0; i < nums.length; i++) {
            real[i] = real[i] - nums[i];
            if(real[i] < 0) {
                return -1;
            }
        }
        // 尽可能多的删除queries但要保证real数组中的值都 >= 0
        int res = 0;
        // 背包？ 视query为物品，real为背包容量, 每个query的价值为1
        // 贪心？按照query长度排序，优先删除长度小的query, 长度相同时，则删除区间后区间内最小值更大的query在前
        List<int[]> queryList = new ArrayList<>(Arrays.asList(queries));
        queryList.sort((a, b) ->{
            if(a[1] - a[0] == b[1] - b[0]) {
                // a：区间内最小值
                int minA = Integer.MAX_VALUE;
                for (int i = a[0]; i <= a[1]; i++) {
                    minA = Math.min(minA, real[i]);
                }
                // b：区间内最小值
                int minB = Integer.MAX_VALUE;
                for (int i = b[0]; i <= b[1]; i++) {
                    minB = Math.min(minB, real[i]);
                }
                return minB - minA;
            }
            return a[1] - a[0] - b[1] + b[0];
        });
        for (int[] query : queryList) {
            int left = query[0], right = query[1];
            boolean flag = true;
            for (int i = left; i <= right; i++) {
                if (real[i] <= 0) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                res++;
                for (int i = left; i <= right; i++) {
                    real[i]--;
                }
            }
        }
        return res;

    }

    public static void main(String[] args) {
//        // [1,0,5,2]
//        //[[0,2],[0,1],[0,0],[1,2],[2,3],[1,3],[1,2],[1,2],[0,0]]
//        int[] nums = {1, 0, 5, 2};
//        int[][] queries = {{0, 2}, {0, 1}, {0, 0}, {1, 2}, {2, 3}, {1, 3}, {1, 2}, {1, 2}, {0, 0}};
//        System.out.println(new Solution().maxRemoval(nums, queries));


        // [0,4,4,0]
        //[[0,0],[3,3],[0,2],[3,3],[0,2],[0,1],[1,1],[1,2],[0,1],[2,3],[0,1],[1,2]]
        int[] nums = {0, 4, 4, 0};
        int[][] queries = {{0, 0}, {3, 3}, {0, 2}, {3, 3}, {0, 2}, {0, 1}, {1, 1}, {1, 2}, {0, 1}, {2, 3}, {0, 1}, {1, 2}};
        System.out.println(new Solution().maxRemoval(nums, queries));

    }
}